package LearnAlgorithm.j_动态规划and贪心算法;

/*
有n个重量和价值分别为wi，vi的物品，从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。
    1 ≤ n ≤ 100
    1 ≤ wi ≤ 100
    1 ≤ vi ≤ 100 
    1 ≤ W ≤ 10000

输入：
    n=4
    (w,v)={(2,3),(1,2),(3,4),(2,2)}
    W=5

输出：
    7（选择第0，1，3号物品）

因为对每个物品只有选和不选两种情况，所以这个问题称为01背包。


5
1 2 3 4 5
1 4 3 4 1
10

12

4
2 1 3 2
3 2 4 2
5

7
 */
import java.util.Scanner;

public class e背包问题byDFSplus01背包 {
	public static void main(String[] args) {
		e背包问题byDFSplus01背包 test = new e背包问题byDFSplus01背包();
		long time = System.currentTimeMillis();
		test.useDFSKnapsack1();
		util.Util.duration(time);
	}
	
	
	public void useDFSKnapsack1() {
		int[] weight = new int[] {1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5};
		int[] value = new int[] {1, 4, 3, 4, 1, 1, 4, 3, 4, 1, 1, 4, 3, 4, 1};
		
		int res = DFSKnapsack(weight, value, 30, 0, 15);
		
		System.out.println(res);
	}
	
	/**
	 * 前置方法
	 * 深搜DFS
	 * DFS不需要打包
	 * DFS也不需要排序
	 */
	public void useDFSKnapsack() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int[] weight = new int[N];
		int[] value = new int[N];
		for (int i = 0; i < N; i++) {
			weight[i] = scanner.nextInt();
		}
		for (int i = 0; i < N; i++) {
			value[i] = scanner.nextInt();
		}
		int maxWeight = scanner.nextInt();
		int res = DFSKnapsack(weight, value, maxWeight, 0, N);
		System.out.println(res);
	}
	
	/**
	 * O(2^N)
不需要回溯的原因是
	我们在一次A使用DFSKnapsack中
	虽然有两次B,C又使用了DFSKnapsack
	但我们在A次的maxWeight，current都没有被改变
	我们传进B,C的动态参数是
		maxWeight - weight[current]
		current + 1
	并没有对A的maxWeight，current造成改变
	所以不需要回溯
	 * @param weight
	 * @param value
	 * @param maxWeight
	 * @param current
	 * @param N
	 * @return
	 */
	public int DFSKnapsack(int[] weight, int[] value, int maxWeight, int current, int N) {
		if (maxWeight <= 0) {//装不进去了；为什么考虑小于？因为考虑到袋子在设置时，最大承重就故意设置0的极端情况
			return 0;
		}
		if (current == N) {//没东西可装了
			return 0;
		}
		int valueNoSelect = DFSKnapsack(weight, value, maxWeight, current + 1, N);//不选择当前的物品A
		if (weight[current] <= maxWeight) {//当前背包足全部容纳A
			int valueSelect = value[current] + DFSKnapsack(weight, value, maxWeight - weight[current], current + 1, N);//选择A
			return Math.max(valueNoSelect, valueSelect);//比较而2种选择的结果
		} else {
			return valueNoSelect;//不足够容纳，直接返回“不选择”的结果
		}
	}
}
